 package statechurn;

import primitives.graph.*;
import translator.DOTWriter;
import java.io.File;

class TraceParser{
	/**
	*
	* FORMAT:
	* [passive]
	* k #NUM
	* [dotoutput]
	* #TRACE
	* 
	* 
	* #NUM : 0-9#NUM | ""
	* #TRACE : (+|-) #CALLS \n
	* #CALLS : "" | "[A-Za-z.0-9_] #CALLS"
	*/
	HashMap<String,Node> nodes = new HashMap<String,Node>();
	int counter = 0;
	
	def static K_RE = ~/k\s+(\d+)/;
	def static TRACE = ~/^(\+|-)/;
	
	public boolean debug = false;
	
	int k = 5;
	
	int merges = 0;
	ArrayList<Node> toremove = new ArrayList<Node>();
	int cacheHits = 0;
	int cacheMisses = 0;
	

	def tailCache = [:]
	


	def sameCache = [:]
	
	def static processTrace(ins){
		for(def i=0; i<ins.length(); i++){
			if(ins.charAt(i) == '+' || ins.charAt(i) == '-'){
				ins= ins.substring(i+1);
				break;
			}
		}

		return ins.tokenize();
	}
	
	def get(){
		def n = new Node("GEN$counter");
		nodes["GEN$counter"] = n;

		
		counter++;
		return n
	}
	
	void connect(name1, name2, label){
		def node1 = get(name1)
		def node2 = get(name2)
		
		node1.connect(node2,label);
		
	}
	
	void pathTo(traces, fromNode){
		def current = fromNode;
		
		def found = false;
		
		while(!traces.isEmpty()){
			def label = traces.pop();
			//print "processing $label "
			def newCurrent = null
			current.transitionsAsT.each{
				if(it.getLabel().equals(label)){
					newCurrent = it.getDestinationNode();
				}
			}
			if(newCurrent == null){
				def newNode = get();
				current.connect(newNode, label);
				current = newNode;
			}else{
				current.connect(newCurrent, label);
				current = newCurrent;
			}

		}
		
	}


	
	
	public tracesOf(Node node, int length){
		
		def stack = []

		def ret = [:]
		stack.push([node, length,ret])
		while(!stack.isEmpty()){
			def (n,l,rtarg) = stack.pop();
			
			if(l > 0){
			
				n.transitionsAsT.each{
					def dest = it.destinationNode
					def target = rtarg.get(it.label, [:])
					stack.push([dest,l-1,target])
				}
			
			}
		}
		return ret;
		
	}

	public boolean equivalent(trace1, trace2){
		if(trace1.size() == 0) return false;

		return (trace1.equals(trace2))
	}
	

	public static testTracesOf(){
		def tp = new TraceParser()
		def g = tp.loadPTAFromTraces(new File("/Users/mat/Dropbox/CommonTraces/test.txt"));
		println("Testing for k=${tp.k}")
		def printed=false
		g.each{
			name, it ->

			if(it.getLabel().equals("Start")){
				println tp.tracesOf(it,tp.k);
				printed = true
				
			}
		}
		if(!printed){
			println("Start wasn't found")
		}
	}
	
	Graph g = new Graph();
	
	public boolean canMerge(Node node1,Node  node2){
		if(node1 == node2) return false;
		if(tailCache[node1.getLabel()] == null) tailCache[node1.getLabel()] = tracesOf(node1,k)
		if(tailCache[node2.getLabel()] == null) tailCache[node2.getLabel()] = tracesOf(node2,k)
		
		def traces1 = tailCache[node1.getLabel()]
		def traces2 = tailCache[node2.getLabel()]
		
		//def names = node1.getLabel() + "_@_" + node2.getLabel()
		def cHit = sameCache.get(node1.getLabel(),[:]).get(node2.getLabel(),null)
		if(cHit == null){
			cacheMisses++
			sameCache[node1.getLabel()][node2.getLabel()] = equivalent(traces1,traces2)
		}else{
			cacheHits++
		}
		
		return sameCache[node1.getLabel()][node2.getLabel()]
	}
	

	
	
	public boolean doStep(){
		def na = null
		def nb = null

		outerloop:
		for(String label1 : nodes.keySet()){
			for(String label2 : nodes.keySet()){
				if(label1 != label2){
					Node n1 = nodes.get(label1)
					Node n2 = nodes.get(label2)
					if(n1.refCount > 0 && n2.refCount > 0)
					if(this.canMerge(n1,n2)){
						na = n1;
						nb = n2
						
						break outerloop; //Great Scott! Awful code!
					}
				}
			}
		}
		

		if(na!=null && nb!= null){
			int om = merges
				replace(nb,na)
				return true
			
		}else{
			return false;
		}
	}
	
	
	def visitedTs = [:]
	
	public void mergenonrecur(Node _to, Transition _from){
		def stack = []
		stack.push([_to,_from])
		while(!stack.isEmpty()){
			def (to,from) = stack.pop();
			if(visitedTs.get(from,false)) continue;
			dbg ("Visiting ${to.label} for ${from.sourceNode.label}=${from.label}=>${from.destinationNode.label}")
			visitedTs[from] = true
			if(!to.hasTransitionWithLabel(from.label)){
				dbg("\t\tconnected ${to.label} to ${from.destinationNode.label}")
				to.connect(from.destinationNode, from.label)
				//from.sourceNode.deleteTransition(from)
			}else{
				Transition t = to.transitionWithLabel(from.label);
				if(t != from){
					if(t.destinationNode == from.destinationNode){
						dbg("\t\tJust deleting $t")
						//from.sourceNode.deleteTransition(from)
					}else{
						from.destinationNode.transitionsAsT.each{
							dbg("\t\tFollowing $it")
							stack.push([t.destinationNode, it])
						}
					}
				}else{
					dbg("Not merging $t with itself")
				}
			}
			
		}
	}
	
	
	public void  merge(Node to, Transition from){
		//Trampoline to mergenonrecur:
		mergenonrecur(to,from) //boing!
		
		return;
		if(visitedTs.get(from,false)) return;
		dbg ("Visiting ${to.label} for ${from.sourceNode.label}=${from.label}=>${from.destinationNode.label}")
		visitedTs[from] = true
		if(!to.hasTransitionWithLabel(from.label)){
			dbg("\t\tconnected ${to.label} to ${from.destinationNode.label}")
			to.connect(from.destinationNode, from.label)
			//from.sourceNode.deleteTransition(from)
		}else{
			Transition t = to.transitionWithLabel(from.label);
			if(t != from){
				if(t.destinationNode == from.destinationNode){
					dbg("\t\tJust deleting $t")
					//from.sourceNode.deleteTransition(from)
				}else{
					from.destinationNode.transitionsAsT.each{
						dbg("\t\tFollowing $it")
						merge(t.destinationNode, it)
					}
				}
			}else{
				dbg("Not merging $t with itself")
			}
		}
	}
	public void replace(Node node,Node with){
		//replace these with loops

		dbg("Merging ${node.label} into ${with.label}")
			
		if(node == with) return;
		for(String l : nodes.keySet()){
			Node n = nodes.get(l)
			
			if(n != null){
				def transitions = n.getTransitionsAsT();
				for(Transition it : transitions){
					
					def target = it.getDestinationNode()
					def label = it.getLabel()

					if(target == node){
						//need to replace it.

						n.deleteTransition(it);

						n.connect(with, label);
						dbg("Connected ${n.label} to ${with.label}")
					}
				}
			}
			
		}
		visitedTs = [:]
		node.transitionsAsT.each{


				merge(with, it)

		}


		nodes.remove(with.getLabel());

		

		tailCache.remove(with.getLabel())
		

		if(!with.label.equals("Start")){
			with.label = "merge$counter"; counter++
		}
		if(node.label.equals("Start")){
			with.label = "Start"
		}
		
		nodes[with.getLabel()] = with

		dbg("\tMerge complete, composite node is now named ${with.label}")

		
		
//		node.transitionsAsT.each{
//			node.deleteTransition(it)
//		}
//		toremove.add(node)
		
		toremove.add(node)
		
		merges++
	}
	
	public void pruneNodes(){

//		nodes.findAll{k ,v -> v.refCount <= 0}.each{k, v -> toremove.add(v)}

		while(!toremove.isEmpty()){
			
			def it = toremove.pop();
			dbg("\tGC:\tgoing to see if $it is removable")
			if(it == null) continue;

			if(it.refCount <= 0){
				if(debug){
					dbgp("\tGC:\tRemoving $it")
				}
				 it.transitionsAsT.each{t->
					toremove.push(t.destinationNode)
					dbgp(", adding ${t.destinationNode.label} to queue")
					it.deleteTransition(t)

				}
				dbg("")
				nodes.remove(it.label)
				tailCache.remove(it.label)
				sameCache.remove(it.label)
			}
		}
		
		toremove = []

	}

	public Graph getGraph(){
		Graph g = new Graph();
		for(String k : nodes.keySet()){
			Node n = nodes.get(k);
			g.addNode(n);
		}
		return g;
	}
	
	
	public Graph doKTails(){
		boolean go = true;
		int iter = 0
		DOTWriter writer = new DOTWriter()
		if(debug) writer.setPrintRefCounts(true)
		int startSize = nodes.size()
		long startTime = System.currentTimeMillis() 
		
		g = getGraph()
		new File("iter${iter}.dot").withWriter { out -> out.writeLine(writer.getRepresentation(g)) }
		long start = System.currentTimeMillis()
		int oldSize = nodes.size();
		while(go){

			iter++
			go = doStep();
			pruneNodes()
			
			if(debug){
				g = getGraph()
				new File("iter${iter}.dot").withWriter { out -> out.writeLine(writer.getRepresentation(g)) }
				
			}


			
			double time = (System.currentTimeMillis() - start) / 1000;
			if(time > 5){
				int size = nodes.size()
				int delta = oldSize - size
				oldSize = size
				int rate = delta/(0.000001+ time)
				System.err.println("$delta merges have been made in ${time}s [$rate/sec], machine has $size nodes.")
			
				start = System.currentTimeMillis()
			}
		}
		g = getGraph()
		def time = (System.currentTimeMillis() - startTime) / 1000;
		long delta = startSize - nodes.size()
		double rate = delta/(0.000001+ time)
		System.err.println("$delta merges have been made in ${time}s [$rate/sec], machine has ${nodes.size()} nodes.")
		new File("final.dot").withWriter { out -> out.writeLine(writer.getRepresentation(g)) }
		
		return g;

	}
	public loadPTAFromTraces(String[] lines){
		def kstmt = lines.find{(K_RE.matcher(it).matches())} 
		def knum = kstmt =~ K_RE
		k =  knum[0][1].toInteger()
                
		def start = new Node("Start");
		nodes['Start'] = start;
		def LOTS = 50000000;
		start.refCount = LOTS;
		def traces = getTraces(lines)
		
		traces.each{
			traceLine -> 
			pathTo(traceLine, start);
		}
	

		return nodes;
	}

	
	def loadPTAFromTraces(File input) throws IOException{
			return loadPTAFromTraces((String[])(input.readLines().toArray()))
	}
	
	def static getTraces(String[] lines){
		def traces = lines.findAll{it =~ TRACE};
		def ret = traces.collect{
			processTrace(it).reverse()
		}
		return ret;		
		
	}
	
	public static void main(String[] args){
		if(args.length > 0 && args[0].equalsIgnoreCase("TestEq")){
			testTracesOf();
			System.exit(1);
		}
		def tp = new TraceParser()
		tp.loadPTAFromTraces(new File(args[0]));
		
		def g = tp.doKTails()
		//println new DOTWriter().getRepresentation(g);
		

	}
	
	public dbg(msg){
		if(debug) println "DEBUG: $msg"
	}
	public dbgp(msg){
		if(debug)println msg
	}
}